package com.sheng.leetcode.year2023.month07.day21;

import lombok.var;
import org.junit.Test;

import java.util.PriorityQueue;

/**
 * @author liusheng
 * @date 2023/07/21
 * <p>
 * 1499. 满足不等式的最大值<p>
 * <p>
 * 给你一个数组 points 和一个整数 k 。数组中每个元素都表示二维平面上的点的坐标，<p>
 * 并按照横坐标 x 的值从小到大排序。也就是说 points[i] = [xi, yi] ，<p>
 * 并且在 1 <= i < j <= points.length 的前提下， xi < xj 总成立。<p>
 * 请你找出 yi + yj + |xi - xj| 的 最大值，其中 |xi - xj| <= k 且 1 <= i < j <= points.length。<p>
 * 题目测试数据保证至少存在一对能够满足 |xi - xj| <= k 的点。<p>
 * <p>
 * 示例 1：<p>
 * 输入：points = [[1,3],[2,0],[5,10],[6,-10]], k = 1<p>
 * 输出：4<p>
 * 解释：前两个点满足 |xi - xj| <= 1 ，代入方程计算，则得到值 3 + 0 + |1 - 2| = 4 。第三个和第四个点也满足条件，得到值 10 + -10 + |5 - 6| = 1 。<p>
 * 没有其他满足条件的点，所以返回 4 和 1 中最大的那个。<p>
 * <p>
 * 示例 2：<p>
 * 输入：points = [[0,0],[3,0],[9,2]], k = 3<p>
 * 输出：3<p>
 * 解释：只有前两个点满足 |xi - xj| <= 3 ，代入方程后得到值 0 + 0 + |0 - 3| = 3 。<p>
 * <p>
 * 提示：<p>
 * 2 <= points.length <= 10^5<p>
 * points[i].length == 2<p>
 * -10^8 <= points[i][0], points[i][1] <= 10^8<p>
 * 0 <= k <= 2 * 10^8<p>
 * 对于所有的1 <= i < j <= points.length ，points[i][0] < points[j][0] 都成立。也就是说，xi 是严格递增的。<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/max-value-of-equation">1499. 满足不等式的最大值</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1499 {

    @Test
    public void test01() {
//        int[][] points = {{1, 3}, {2, 0}, {5, 10}, {6, -10}};
//        int k = 1;
        int[][] points = {{0, 0}, {3, 0}, {9, 2}};
        int k = 3;
        System.out.println(new Solution().findMaxValueOfEquation(points, k));
    }
}

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        int n = points.length;
        int ans = Integer.MIN_VALUE;
        // 暴力破解，超时
//        for (int i = 0; i < n; i++) {
//            for (int j = i + 1; j < n; j++) {
//                if (points[j][0] - points[i][0] <= k) {
//                    ans = Math.max(ans, points[j][0] - points[i][0] + points[i][1] + points[j][1]);
//                }
//            }
//        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (var p : points) {
            int x = p[0], y = p[1];
            while (!pq.isEmpty() && x - pq.peek()[1] > k) {
                pq.poll();
            }
            if (!pq.isEmpty()) {
                ans = Math.max(ans, x + y + pq.peek()[0]);
            }
            pq.offer(new int[]{y - x, x});
        }
        return ans;
    }
}
